Thuật toán Sàng Atkin

  • Tất cả các số dư là số dư khi chia cho sáu mươi (chia cho 60 và xét số dư).
  • Tất cả các số, bao gồm cả x và y đều là số nguyên dương.
  • Đảo một ô trong sàng nghĩa là thay đổi đánh dấu (là số nguyên tố hoặc không) thành ngược lại.
  1. Tạo bảng kết quả, điền vào 2, 3, và 5.
  2. Tạo bảng sàng nguyên tố với các số nguyên dương; tất cả các số đánh dấu là không nguyên tố.
  3. Với tất cả các số trong sàng:
    • Nếu số đó chia 60 dư 1, 13, 17, 29, 37, 41, 49, hoặc 53, đảo đánh dấu cho các số ở 4 ∗ x 2 + y 2 {\displaystyle 4*x^{2}+y^{2}} = số đang xét.
    • Nếu số đó chia 60 dư 7, 19, 31, hoặc 43, đảo các ô 3 ∗ x 2 + y 2 {\displaystyle 3*x^{2}+y^{2}} = số đang xét.
    • Nếu số đó chia 60 dư 11, 23, 47, hoặc 59, đảo các số 3 ∗ x 2 − y 2 {\displaystyle 3*x^{2}-y^{2}} = số đang xét.
    • Còn lại, không làm gì cả
  4. Bắt đầu từ số nhỏ nhất trong sàng.
  5. Lấy các số tiếp theo trong sàng được đánh dấu là prime.
  6. Thêm vào danh sách kết quả.
  7. Bình phương số đó và đánh dấu các bội số của số đó là không phải số nguyên tố.
  8. Lặp lại bước 5 cho tới bước 8.